package mrHunter.puzzles.graph;

public class Puzzle1 {
    //Connected Graph
    public String connectedGraph(String input){
        //int[][] G
        //boolean y
        String[] rows=input.split("%");
        int v=rows.length;
        int[][] G=new int[v][v];
        boolean[] visited=new boolean[v];
        for(int i=0;i<v;i++)
            visited[i]=false;

        for(int i=0;i<v;i++){
            String[] cols=rows[i].split(" ");
            for(int j=0;j<v;j++){
                G[i][j]=Integer.parseInt(cols[j]);
            }
        }

        int count=0;
        for (int i=0;i<v;i++){
            if(!visited[i]){
                DFS(i,visited,G);
                count++;
            }
        }
        if(1 == count)
            return "true";
        else
            return "false";
    }

    private void DFS(int i, boolean[] visited, int[][]G){
        for(int j=0;j<visited.length;j++){
            if(1==G[i][j]&&!visited[j]){
                visited[j]=true;
                DFS(j,visited,G);
            }
        }
    }
}
